//
//  coin.h
//  coin
//
//  Created by Wong Hui Hern on 2023/12/22.
//

#ifndef coin_h
#define coin_h

#include<iostream>
#include<vector>
#include<climits>

using namespace std;

class coin{
private:
    int n;
    int c1,c5,c10,c25;
public:
    coin(int _n):n(_n){};
    coin(int _n,int _c1,int _c5,int _c10,int _c25):n(_n),c1(_c1),c5(_c5),c10(_c10),c25(_c25){};
    int fcounting();
    int counting(int nn,const vector<int>& coins);
    int back_counting();
    void get_count();
};

int coin::fcounting(){
    int cnt=0;
    int flag=1;
    int nn=n;
    if(c1+5*c5+10*c10+25*c25<nn){
        return -1;
    }
    else{
        while(nn!=0){
            if(nn>=25&&c25>0){
                cnt++;
                c25--;
                nn-=25;
            }
            else if(nn>=25&&c25==0){
                if(nn>=10&&c10>0){
                    cnt++;
                    c10--;
                    nn-=10;
                }
                else if(nn>=10&&c10==0){
                    if(nn>=5&&c5>0){
                        cnt++;
                        c5--;
                        nn-=5;
                    }
                    else if(nn>=1&&c1>0){
                        cnt++;
                        c1--;
                        nn-=1;
                    }
                }
            }
            else if(nn>=10&&c10>0){
                cnt++;
                c10--;
                nn-=10;
            }
            else if(nn>=10&&c10==0){
                if(nn>=5&&c5>0){
                    cnt++;
                    c5--;
                    nn-=5;
                }
                else if(nn>=1&&c1>0){
                    cnt++;
                    c1--;
                    nn-=1;
                }
            }
            else if(nn>=5&&c5>0){
                cnt++;
                c5--;
                nn-=5;
            }
            else if(nn>=5&&c5==0){
                if(nn>=1&&c1>0){
                    cnt++;
                    c1--;
                    nn-=1;
                }
            }
            else if(nn>=1&&c1>0){
                cnt++;
                c1--;
                nn-=1;
            }
            else if(nn>=1&&c1==0){
                flag=0;
                break;
            }
        }
        if(flag==1){
            return cnt;
        }
        else return -1;
    }
}

int coin::counting(int nn, const vector<int>& coins){
    vector<int> a(nn+1,INT_MAX);
    a[0]=0;
    for(int i:coins){
        for(int j=i;j<=nn;j++){
            if(a[j-1]!=INT_MAX){
                a[j]=min(a[j],a[j-i]+1);
            }
        }
    }
    if(a[nn]==INT_MAX){
        return -1;
    }
    else{
        return a[nn];
    }
}

int coin::back_counting(){
    int nn=n;
    int cnt=0;
    if(nn==0){
        cnt=0;
    }
    while(nn!=0){
        if(nn>=25){
            cnt++;
            nn-=25;
        }
        else if(nn>=10&&nn<25){
            cnt++;
            nn-=10;
        }
        else if(nn>=5&&nn<10){
            cnt++;
            nn-=5;
        }
        else if(nn>=1&&nn<5){
            cnt++;
            nn-=1;
        }
    }
    return cnt;
}

#endif /* coin_h */
